//lc


//https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden/


//区间覆盖 类似于基础课 https://www.acwing.com/problem/content/909/


//pair存每个区间覆盖的范围
#define x first
#define y second

typedef pair<int, int> PII;

class Solution
{
public:
    int minTaps(int n, vector<int> &ranges)
    {
        vector<PII> q;
        for (int i = 0; i < ranges.size(); i ++ )
        {
            q.push_back({i - ranges[i], i + ranges[i]});
        }
        sort(q.begin(), q.end());
        int res = 0, r = 0;
        for (int i = 0; i < q.size(); i ++ )
        {
            int j = i, mr = -1;
            while (j < q.size() && q[j].x <= r) mr = max(mr, q[j ++ ].y);
            if (mr == -1) return -1;
            res ++ ;
            if (mr >= n) return res;
            r = mr;
            i = j - 1;
        }

        return -1;
    }
};
